/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    /*
    定义两个快慢指针，快指针指向第n个结点，慢指针指向第一个结点
    两个指针开始同时走，
    当快指针走到末尾了，此时慢指针指向倒数第n个结点
    删除即可
    */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        auto fast=head;
        auto slow=head;
        ListNode* pre=slow;
        while(--n)
        {
            fast=fast->next;
        }
        while(fast->next)
        {
            pre=slow;
            slow=slow->next;
            fast=fast->next;
        }
        if(slow==head)
            return head->next;
       pre->next=slow->next;
        free(slow);
        return head;
    }
};